package com.xgh.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName Offer03
 * @Description
 * @Author xinggh
 * @Date 2020/6/28 9:40
 * @Version 1.0
 **/
public class Offer03 {
    /**
     * 剑指 Offer 03. 数组中重复的数字
     * 找出数组中重复的数字。
     * <p>
     * <p>
     * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
     * <p>
     * 示例 1：
     * <p>
     * 输入：
     * [2, 3, 1, 0, 2, 5, 3]
     * 输出：2 或 3
     * <p>
     * <p>
     * 限制：
     * <p>
     * 2 <= n <= 100000
     */
    //1、直接循环遍历数组，找出重复的数值直接返回吗，否则的话返回-1；时间复杂度为o(n2)
    public int findRepeatNumber1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[i]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }

    /**
     * 2、使用集合遍历数组到set 如果有重复则返回
     *
     * @param nums
     * @return
     */
    public int findRepeatNumber2(int[] nums) {
        Set set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return nums[i];
            }
           /* if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);*/
        }
        return -1;
    }
}
